package com.cat.binaryTree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
 * @create 2025/9/30 19:55
 * @since JDK17
 */

public class Solution96 {
    class Info {
        TreeNode node;
        int pos;

        public Info(TreeNode node, int pos) {
            this.node = node;
            this.pos = pos;
        }
    }
    public boolean isCompleteTree(TreeNode root) {
        Deque<Info> q = new ArrayDeque<>();
        int cnt = 0, code = 0;
        q.add(new Info(root, 1));
        while (!q.isEmpty()) {
            var x = q.poll();
            code = x.pos;
            if (x.node.left != null) {
                q.add(new Info(x.node.left, x.pos * 2));
            }
            if (x.node.right != null) {
                q.add(new Info(x.node.right, x.pos * 2 + 1));
            }
            cnt++;
        }

        return cnt == code;
    }
}
